#include "FloydAlgSeq.h"

#define eps 0.0000001

void floydSequential( int n, int* d )
{
	for (int k=0; k<n; k++)
		for (int i=0; i<n; i++)
			for (int j=0; j<n; j++)
				if (d[i*n+k]>=0 && d[k*n+j]>=0)
					if ((d[i*n+j] > (d[i*n+k] + d[k*n+j])) || ( d[i*n+j]<0) )
						d[i*n+j] =  d[i*n+k] + d[k*n+j]; 				

}


void floydMPI(int n, int* d)
{
	int rank, size;
	MPI_Comm_size(MPI_COMM_WORLD, &size);
	MPI_Comm_rank(MPI_COMM_WORLD, &rank);

	int blockAmount = (int)sqrt(double(size));

	int blockSize = n/blockAmount;
	if (n % blockAmount != 0)
		blockSize++;

	int * buf = new int[blockSize * blockSize];
	int * tmp = new int[n * n];

	MPI_Status status;

	for (int k = 0; k < n; k++)
	{	
		// fill buf 
		//printf("I am %i, k = %i and buf = \n", rank, k);
		for (int i = 0; i < blockSize; i++)
		{
			for (int j = 0; j < blockSize; j++)
			{
				buf[i * blockSize + j] = d[n * (blockSize * (rank / blockSize) + i) + j + blockSize * (rank % blockSize)];
				//printf("%i ", buf[i * blockSize + j]);
			}
			//printf("\n");
		}
		//fflush(stdout);
		// compute buf

		for (int i = 0; i < blockSize; i++)
			for (int j = 0; j < blockSize; j++)
				if (d[n * (blockSize * (rank / blockSize) + i) + k] >= 0 && d[n * k + j + blockSize * (rank % blockSize)] >= 0)
					if ((buf[i * blockSize + j] > (d[n * (blockSize * (rank / blockSize) + i) + k] + d[n * k + j + blockSize * (rank % blockSize)])) || ( buf[i * blockSize + j] < 0) )
						buf[i * blockSize + j] =  d[n * (blockSize * (rank / blockSize) + i) + k] + d[n * k + j + blockSize * (rank % blockSize)];

		/*printf("I am %i, k = %i and buf = \n", rank, k);
		for (int i = 0; i < blockSize; i++)
		{
			for (int j = 0; j < blockSize; j++)
			{
				printf("%i ", buf[i * blockSize + j]);
			}
			printf("\n");
		}
		printf("\n");*/

		//MPI_Bcast(buf, blockSize * blockSize, MPI_INT, rank, MPI_COMM_WORLD);
		MPI_Barrier(MPI_COMM_WORLD);
		MPI_Allgather(buf, blockSize * blockSize, MPI_INT, tmp, blockSize * blockSize, MPI_INT, MPI_COMM_WORLD);

		// fill d

		for (int p = 0; p < size; p++)
		{
			for (int i = 0; i < blockSize; i++)
			{
				for (int j = 0; j < blockSize; j++)
				{
					d[n * (blockSize * (p / blockSize) + i) + j + blockSize * (p % blockSize)] =
						tmp[n * p + i * blockSize + j];
				}
			}
		}

		/*printf("I am %i, k = %i and d = \n", rank, k);
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
			{
				printf("%i ", d[i * n + j]);
			}
			printf("\n");
		}
		printf("\n");
		MPI_Barrier(MPI_COMM_WORLD);*/
	}
	MPI_Barrier(MPI_COMM_WORLD);
}

		//printf("k = %i\n", k);
		//fflush(stdout);
		//if (rank == 0)
		//{
		//	for (int p = 0; p < size; p++)
		//	{
		//		//// fill buf
		//		for (int i = 0; i < blockSize; i++)
		//			for (int j = 0; j < blockSize; j++)
		//			{
		//				buf[i * blockSize + j] = d[n * (p * blockSize + i) + j + p * blockSize];
		//			}
		//		printf("fill buf ok\n");
		//		fflush(stdout);

		//		/// fill k
		//		for (int j = 0; j < blockSize; j++)
		//		{
		//			kCol[j] = d[n * (p * blockSize + j) + k];
		//			kRow[j] = d[n * k + j + p * blockSize];
		//		}

		//		printf("fill k ok\n");
		//		fflush(stdout);

		//		MPI_Pack( buf, blockSize * blockSize, MPI_INT, tempBuf, sizeof(tempBuf), tempBuf, MPI_COMM_WORLD );
		//		MPI_Pack( kCol, blockSize, MPI_INT,  tempBuf, sizeof(tempBuf), tempBuf + blockSize * blockSize, MPI_COMM_WORLD );
		//		MPI_Pack( kRow, blockSize, MPI_INT,  tempBuf, sizeof(tempBuf), tempBuf + blockSize * blockSize + blockSize, MPI_COMM_WORLD );

		//		printf("pack ok\n");
		//		fflush(stdout);

		//		MPI_Send(tempBuf, blockSize, MPI_INT, p, 0, MPI_COMM_WORLD); 

		//		printf("send ok\n");
		//		fflush(stdout);
		//	}
		//}

		//MPI_Recv(tempBuf, genSize, MPI_INT, 0, 0, MPI_COMM_WORLD, &status);

		//printf("resv ok\n");
		//fflush(stdout);

		//MPI_Unpack(tempBuf, genSize, tempBuf, buf, blockSize * blockSize, MPI_INT, MPI_COMM_WORLD);
		//MPI_Unpack(tempBuf, genSize, tempBuf + blockSize * blockSize, kCol, blockSize, MPI_INT, MPI_COMM_WORLD); 
		//MPI_Unpack(tempBuf, genSize, tempBuf + blockSize * blockSize + blockSize, kRow, blockSize, MPI_INT, MPI_COMM_WORLD); 

		//printf("unpack ok\n");
		//fflush(stdout);

		//for (int i = 0; i < blockSize; i++)
		//	for (int j = 0; j < blockSize; j++)
		//		if (kCol[i] >= 0 && kRow[j] >= 0)
		//			if ((buf[i * blockSize + j] > (kCol[i] + kRow[j])) || ( buf[i * blockSize + j] < 0) )
		//				buf[i * blockSize +j] =  kCol[i] + kRow[j];

		//printf("alg ok\n");
		//fflush(stdout);

		//MPI_Barrier(MPI_COMM_WORLD);

		///// Rewrite d
		//for (int i = 0; i < blockSize; i++)
		//	for (int j = 0; j < blockSize; j++)
		//	{
		//		d[n * (rank * blockSize + i) + j + rank * blockSize] = buf[i * blockSize + j];
		//	}

		//printf("rewrite ok\n");
		//fflush(stdout);

